/**
 * 希尔排序
 *
 * 利用间隔及分组方式，减少交换次数，从宏观上达到有序，再微调
 */
public class ShellSort extends TemplateSort {

    @Override
    void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, 121, 363, 1093
        }

        while (h >= 1) {
            // 将数组变成h有序
            for (int i = h; i < N; i++) {
                // 将 a[i] 插入到a[i-h],a[i-2*h],a[i-3*h]...之中
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                   exch(a, j, j-h);

                    // 显示排序过程及交换次数
//                    show(a);
                }
            }
            h = h / 3;
        }
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new ShellSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }

}
